// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-07 00:18
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

public class MergeTrees {
    /**
     * 合并二叉树 -> 遍历的同时创建一棵新树
     */


    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return inOrder(root1, root2);
    }

    /**
     * 实现二叉树中序遍历的时候完成二叉树的合并
     *
     * @param root1 二叉树根节点1
     * @param root2 二叉树根节点2
     * @return
     */
    private TreeNode inOrder(TreeNode root1, TreeNode root2) {
        if (root1 == null && root2 == null) {
            // 两个节点同时为空
            return null;
        }
        TreeNode res;
        if (root1 != null && root2 != null) {
            res = new TreeNode(root1.val + root2.val);
        } else {
            // 两个树当前节点有一棵树是空
            res = (root1 == null ? new TreeNode(root2.val) : new TreeNode(root1.val));
        }

        res.left = inOrder(root1 == null ? null : root1.left, root2 == null ? null : root2.left);
        res.right = inOrder(root1 == null ? null : root1.right, root2 == null ? null : root2.right);
        return res;
    }

    @Test
    public void shout() {
        int[] nodesO = {1, 3, 2, 5};
        int[] nodesT = {2, 1, 3, -1, 4, -1, 7};
//        int[] nodesO = {1, 2};
//        int[] nodesT = {2, 2};
        Utils utils = new Utils();
        TreeNode<Integer> root1 = utils.constructTreeBySequence(nodesO);
        TreeNode<Integer> root2 = utils.constructTreeBySequence(nodesT);
        utils.preSearch(mergeTrees(root1, root2));
    }

}
